from myro import *
from copy import *
from time import *
from sys import *

shortestDist = 0
shortestPath = []



def getDeliveries():
    class node:
        def __init__(self, name, path, thisDrop, dlvrs, endpt, gval, hval, fval):
            self.name = name
            self.path = path
            self.thisDrop = thisDrop
            self.dlvrs = dlvrs
            self.endpt = endpt
            self.gval = gval
            self.hval = hval
            self.fval = fval

        def get_name(self):
            return self.name
        def get_path(self):
            return self.path
        def get_thisDrop(self):
            return self.thisDrop
        def get_dlvrs(self):
            return self.dlvrs
        def get_endpt(self):
            return self.endpt
        def get_gval(self):
            return self.gval
        def get_hval(self):
            return self.hval
        def get_fval(self):
            return self.fval

    global shortestDist
    global shortestPath

    def picksOf(pairList):
        return map(zth,pairList)

    def zth(pair):
        return pair[0]

    def dropsOf(pairList):
        return map(oneth, pairList)

    def oneth(pair):
        return pair[1]

    def getDist():
        #Opens the file with the distance information
        f = open("Large\Labeled Table.txt", "r")
        #Reads one line of the file and stores it into line
        line = f.readline()
        #returns the items in line into an array
        bldgOrder = line.split()
        #displays the items in bldgOrder
        #print bldgOrder
        # Loops through the length of building order
        for i in range(len(bldgOrder)):
            #Reads the next line of code
            line = f.readline()
            #print line
            distances = line.split()
            rowStart = distances[0]
            #Creates a new entry in the dictionary
            distList[rowStart] = {}
            #Deletes the first distance which is the building name. This is to map correctly.
            del(distances[0])
            for j in range(len(distances)):
                distList[rowStart][bldgOrder[j]] = int(distances[j])
        for k in range(len(bldgOrder)):
            0
            #print bldgOrder[k]
            #print distList[bldgOrder[k]]

    def getShortest(distList, deliveries):
        class nodeName:
            def __init__(self):
                self.name = 0

            def next(self):
                self.name = self.name + 1
                return self.name

        def sortList(left,right):
            if left.get_fval() < right.get_fval():
                return -1
            elif left.get_fval() == right.get_fval():
                return 0
            else:
                return 1
            
        def makeNode(thisDlv,dds,ppath,frm,dlvs,endpt,gg):
            pickup = thisDlv[0]
            dropoff = thisDlv[1]
            newg = gg + dds[frm][pickup]
            newDlvs = deepcopy(dlvs)
            newDlvs.remove(thisDlv)
            newPath = ppath + [thisDlv]
            if newDlvs:
                hval = heuristic(dropsOf(newDlvs)+[dropoff],picksOf(newDlvs),endpt,dds)
                return node(name.next(),newPath,dropoff,newDlvs,endpt,newg,hval,newg+hval)
            else:
                newg += dds[dropoff][endpt]
                hval = 0
                newPath += [endpt]
            return node(name.next(),newPath,endpt,newDlvs,'',newg,hval,newg+hval)   

        def pq(nodeList):
            smallest = 0

            for i in range(len(nodeList)):
                if nodeList[i].get_fval() < nodeList[smallest].get_fval():
                    smallest = i

            temp = nodeList[0]
            nodeList[0] = nodeList[smallest]
            nodeList[smallest] = temp
            
        def heuristic(dropOffs,pickUps,endPoint,distList):        
            smallestDist = []
            heurDist = []
            endDist = maxint
            heurTotal = 0

            for i in range(len(dropOffs)):
                x = maxint
                for j in range(len(pickUps)):
                    dist = distList[ dropOffs[i]][ pickUps[j]]
                    #x = dist if(dist<x) else x
                    if dist < x:
                        x = dist
                smallestDist.append(x)

            for i in range(len(smallestDist)-1):
                x = 0
                for j in range(len(smallestDist)):
                    #x = j if smallestDist[j]<smallestDist[x] else x
                    if smallestDist[j]<smallestDist[x]:
                        x = j
                heurDist.append(smallestDist[x])
                del(smallestDist[x])

            for i in range(len(dropOffs)):
                #endDist = distList[dropOffs[i]][endPoint] if distList[dropOffs[i]][endPoint]<endDist else endDist
                if distList[dropOffs[i]][endPoint]<endDist:
                    endDist = distList[dropOffs[i]][endPoint]

            for i in range(len(heurDist)):
                heurTotal = heurTotal + heurDist[i]

            heurTotal = heurTotal + endDist
            return heurTotal

        #array of nodes sorted by lowest f values
        nodeList = []
        name = nodeName()
        shortestFound = 0
        possShortDistFound = 0
        currentShortest = None

        start = node(name.next, [], 'OM', deliveries, 'OM', 0, 0, 0)
        nodeList.append(start)

        while(shortestFound == 0):
            #if(possShortDistFound == 1):
                #print "Found Length " , currentShortest.get_fval(), " Next Shortest ", nodeList[0].get_fval()
            if currentShortest != None:
                if currentShortest.get_fval() < nodeList[0].get_fval():
                    #print "found shortest"
                    #print currentShortest.get_path()
                    return currentShortest
                
            curr = nodeList[0]
            dlvrs = curr.get_dlvrs()
            del(nodeList[0])
            
            #expanding the nodes
            for i in range(len(dlvrs)):
                child = makeNode(dlvrs[i],distList,curr.get_path(),curr.get_thisDrop(),dlvrs,curr.get_endpt(),curr.get_gval())
            
                if child.get_endpt() == "":
                    if currentShortest == None:
                        currentShortest = child
                        possShortDistFound = 1
                        #print currentShortest.get_path()
                        #print "found path"
                    elif child.get_fval() < currentShortest.get_fval():
                        currentShortest = child
                        #print "found shorter"
                else:
                    nodeList.append(child)

            #nodeList.sort(sortList)
            pq(nodeList)

    def ub(distList, deliveries):
        picks = picksOf(deliveries)
        drops = dropsOf(deliveries)
        distTab = []
        total = 0
        amt = len(deliveries) + 2
        avg = 0
        possible = 0
        picks.insert(0, 'OM')
        drops.insert(0, 'OM')
        print "picks: " , picks
        print "Drops: " , drops
        for i in range(len(picks)):
            distTab.append([])
            for j in range(len(drops)):
                distTab[i].append(distList[drops[j]][picks[i]])
                possible = possible + 1

        print distTab
        while(not distTab == []):
            highest = [0,0]
            lowest = [0,0]
            for i in range(len(picks)):
                for j in range(len(drops)):
                    #print i, ":", j
                    if distTab[i][j] > distTab[highest[0]][highest[1]]:
                        highest[0] = i
                        highest[1] = j

            lowest[0] = highest[0]
            lowest[1] = highest[1]
            for i in range(len(distTab)):
                if distTab[highest[0]][i] < distTab[lowest[0]][lowest[1]]:
                    lowest[0] = highest[0]
                    lowest[1] = i
            for i in range(len(distTab[i])):
                if distTab[i][highest[1]] < distTab[lowest[0]][lowest[1]]:
                    lowest[0] = i
                    lowest[1] = highest[1]

            total = total + distTab[lowest[0]][lowest[1]]

            #print "Highest :", distTab[highest[0]][highest[1]]
            #print "Lowest :", distTab[lowest[0]][lowest[1]]
            del picks[lowest[0]]
            del drops[lowest[1]]
            del distTab[lowest[0]]
            for i in range(len(distTab)):
                del distTab[i][lowest[1]]

            #print distTab

        return total

    def perms(fullPath, togo, distList):
        togolen = len(togo)
        currelem = len(fullPath)
        if(togolen == 0):
            #print fullPath
            checkDist(fullPath, distList)
            0
        else:
            for i in range(togolen):
                #print togo[i]
                perms(fullPath + [togo[i]], togo[0:i] + togo[i+1:togolen+1], distList)

    def checkDist(fullPath, distList):
        global shortestDist
        global shortestPath
        #print fullPath[0]
        totalTime = distList['OM'][fullPath[0][0]]
        for i in range(len(fullPath) - 1):
            totalTime += distList[fullPath[i][1]][fullPath[i + 1][0]]
        totalTime += distList[fullPath[len(fullPath)-1][1]]['OM']
        if(shortestDist == 0):
            shortestDist = totalTime
            shortestPath = fullPath
        elif(totalTime < shortestDist):
            shortestDist = totalTime
            shortestPath = fullPath
            #print shortestDist
            #print shortestPath

    #dictionary of distances
    distList = {}
    #fill the dictionary of distances
    getDist()
    #deliveries array
    deliveries = []
    #get deliveries from file
    #fname = raw_input("Whcich file would you like to open? ")
    files = ['dlvProb-7A.txt', 'dlvProb-4A.txt','dlvProb-5A.txt','dlvProb-5B.txt','dlvProb-5C.txt', 'dlvProb-8A.txt' ]
    for fname in files:
        print fname
        dels = open('Large\\' + fname)
        delItem = dels.readline().rstrip()
        while(delItem != ""):
            delItemList = delItem.split(" ")
            deliveries.append(delItemList)
            delItem = dels.readline().rstrip()
        shortestDist
        shortestPath
        #gen perms
        start = clock()
        perms([], deliveries, distList)
        end = clock()
        print "It took " , (end - start), " seconds"
        print shortestPath
        print shortestDist
        start = clock()
        #upper = ub(distList, deliveries)
        shortest = getShortest(distList, deliveries)
        end = clock()
        #print "\nUpper Bound: " , upper
        print "It took " , (end - start), " seconds"
        print shortest.get_path()
        print shortest.get_fval(), "\n\n\n"
